/*
    二分搜索/二分查找
    前提： 数组是有序数组 例如： [1,2,3,4,5]
    思路: 
        1. 首先将数组进行折半， 分成左右两边数组， 找出中间元素
        2. 目标值与中间值进行比较， 如果相等直接返回
        3. 如果目标值小于中间值， 则左边数组进行递归，
        4. 如果目标值大于中间值， 则右边数组进行递归

    思路2:
        1. 定义start 和 end， 找到中点的值
        2. 进行遍历 如果start<end， 有以下三种情况
        3. 如果target === 中值， 直接返回下标
        4. 如果target>中值， 那么挪动start的位置 = mid+1
        5. 如果target<中值， 那么挪动end坐标 = mid
        6. 如果都没有找到， 返回-1
        7. 记住， 二分查找只只用于有序排列的组合。
*/

let arr = [1,2,3,4,5,6,7]
let target = 6

function search(arr, target) {
    let start = 0
    let end = arr.length

    while(start < end) {
        let mid = Math.floor((end + start) / 2)

        if (arr[mid] === target) {
            return mid
        }

        if (arr[mid] > target) {
            end = mid
        }

        if (arr[mid] < target) {
            start = mid + 1
        }
    }
    return -1
}
console.log(search(arr, target))


// 写错了， 作废， 留个记录
// function midSearch(arr, target) {
//     if (arr.length <= 1) return arr

//     let minIndex = Math.floor(arr.length / 2)
//     let minEle = arr[minIndex]

//     let left = arr.splice(0, minIndex)
//     let right = arr.splice(1)
//     // console.log(left, right)

//     if (target === minEle) return minIndex

//     for(let i=0; i<arr.length; i++) {
//         if(target > minEle) {
//             return midSearch(left, target)
//         } else {
//             return midSearch(right, target)
//         }
//     }
// }
// console.log(midSearch(arr, target))

